#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2021/5/14 14:57
# @Author  : hqu-jcl
# @Site    : 
# @File    : nfa_2_dfa.py

import re
import numpy as np
import pandas as pd


def is_equal(new_partition, initial_partition):
    """
       判断两个划分是否相等
    :param new_partition:
    :param initial_partition:
    :return:
    """
    state_set_new = []
    state_set_init = []

    for i in range(len(new_partition)):
        temp = []
        for j in range(len(new_partition[i])):
            temp.append(new_partition[i][j][2])
        state_set_new.append(temp)

    for i in range(len(initial_partition)):
        temp = []
        for j in range(len(initial_partition[i])):
            temp.append(initial_partition[i][j][2])
        state_set_init.append(temp)

    if len(state_set_init) != len(state_set_new):
        return False

    # 对每个进行排序
    for i in range(len(state_set_new)):
        state_set_new[i].sort()
        state_set_init[i].sort()

    data = []
    for i in range(len(state_set_init)):
        for j in range(len(state_set_new)):
            if state_set_init[i] == state_set_new[j]:
                data.append(state_set_new[j])
    if len(data) == len(state_set_new):
        return True
    else:
        return False


def nfa_2_dfa(NFA: np.ndarray, character_set: list,start_state,end_state):
    """
    input nfa,return min_dfa
    :return: dfa
    """

    def move(t, param):
        """
        :param t:  状态
        :param param: 字符
        :return: 转移后状态
        """
        index = character_set.index(param)  # 取索引
        return NFA[t][index]  # return 对应状态以及输入下的跳转状态

    def epsilon_closure(state):
        """
        求 ε-闭包
        :param state: 状态
        :return: 闭包
        """
        _U = []
        stack = []
        for t in state:
            _U.append(t)
            stack.append(t)  # 入栈

        while len(stack) > 0:
            t = stack.pop()
            u_set = move(t, '')  # 空跳转
            for u in u_set:
                if u not in _U:
                    _U.append(u)
                    stack.append(u)
        return _U

    def smove(states: list, c):
        """
        状态转移
        :param states:
        :param c:
        :return:
        """
        states_set = []
        for state in states:
            for item in move(state, c):
                states_set.append(item)
        if states_set != []:
            states_set = list(set(states_set))
        states_set.sort()
        return states_set

    def not_in_Dstates(U, Dstates):
        """
         状态是否在状态集中
        :param U:
        :param Dstates:
        :return:
        """
        U[0].sort()
        for i in Dstates:
            i[0].sort()
            if U[0] == i[0]:
                return False
        return True

    def have_finish(Dstate):
        """
        是否完全标记
        :param Dstate:
        :return:
        """
        for k in Dstate:
            if k[1] == 0:
                return False
        return True

    s0 = [start_state]  # 初始状态
    Dstates = [[epsilon_closure(s0), 0]]  # [[状态,标记与否,状态序号],] 0未标记 1标记, 同样需要用到NFA
    Dtran = []  # 未规范的
    while not have_finish(Dstates):
        for i in Dstates:
            if i[1] == 0:
                for j in character_set:
                    if j != '':
                        U = [epsilon_closure(smove(i[0], j)), 0]  # state，需要用到NFA
                        i[1] = 1
                        if not_in_Dstates(U, Dstates) and U[0]:
                            Dstates.append(U)
                        if i[0]:
                            Dtran.append([i[0], j, U])  # 状态+字符=转换后状态
    # 后处理

    # 状态标记处理
    for i in range(len(Dstates)):
        Dstates[i].append(i)

    def minimize_dfa(dfa, D_states,end_state):
        # 初始划分
        initial_partition = [[],[]]
        temp = []
        # 初始划分需要用终态
        for i in D_states:
            if end_state in i[0]:
                initial_partition[1].append(i) # 终态集
            else:
                initial_partition[0].append(i)
        # 利用可区分概念进行划分
        end_partition=initial_partition[1]
        new_partition = []
        while new_partition == [] or not is_equal(new_partition, initial_partition):
            if new_partition!=[]:
                initial_partition = new_partition
                new_partition = []

            for i in range(len(initial_partition)):
                if len(initial_partition[i]) > 1:
                    # print(initial_partition[i])
                    # print("初始")
                    for state in initial_partition[i]:
                        temp_partition = []
                        state_set = []
                        for s in initial_partition[i]:
                            state_set.append(s[0])

                        for _state in dfa:
                            if state[0] == _state[0] and _state[2] not in state_set and state not in temp_partition:
                                temp_partition.append(state)
                        new_partition.append(temp_partition)
                elif len(initial_partition[i])==1:
                    new_partition.append(initial_partition[i])
                else:
                    pass
        # print("划分后")
        # print(new_partition)

        # print("修改状态编号后")
        for k in range(len(new_partition)):
            for j in range(len(new_partition[k])):
                new_partition[k][j][2] = k
            # print(new_partition[k])
        # print(new_partition)
        # print("new ")
        # print(new_partition)
        # print("重新构造DFA")
        data_arr = np.zeros(len(new_partition) * (len(character_set) - 1)).reshape(len(new_partition),
                                                                                   len(character_set) - 1)
        for i in range(data_arr.shape[0]):
            for j in range(data_arr.shape[1]):
                data_arr[i,j]=-1
        DFA = pd.DataFrame(data_arr, dtype=object)
        for i in range(len(new_partition)):
            for j in range(len(new_partition[i])):
                for k in range(len(dfa)):
                    if dfa[k][0] == new_partition[i][j][0]:
                        index = character_set.index(dfa[k][1])
                        DFA.iloc[i][index - 1] = dfa[k][2][0]
        # print(DFA)
        # print("修改编号")
        # print(DFA.shape)
        for i in range(DFA.shape[0]):
            for j in range(DFA.shape[1]):
                for k in range(len(new_partition)):
                    for s in range(len(new_partition[k])):
                        if new_partition[k][s][0] == DFA.iloc[i][j]:
                            DFA.iloc[i][j] = new_partition[k][s][2]
        # print(DFA)

        end_states=[]
        for i in end_partition:
            end_states.append(i[2])

        return DFA,end_states

    # 测试样例终态是3

    DFA,end = minimize_dfa(Dtran, Dstates,end_state)
    DFA.columns = character_set[1:]
    for i in range(DFA.shape[0]):
        for j in range(DFA.shape[1]):
            if DFA.iloc[i][j]==[]:
                DFA.iloc[i][j]='-'
    return DFA,end


# 测试DFA
def test_DFA(DFA, sequence,end_states):
    """
     测试DFA
    :param DFA:
    :param sequence:
    :param end_states:
    :return:
    """
    # 拆分序列
    s = re.split('', sequence)[1:-1]
    print('测试序列：', s)

    # 初始状态
    state = 0
    print('状态转移：', state, end='==>')
    for i in range(len(s)):

        if s[i] not in DFA.columns:
            print(format('\n第{0}个字符{1}不符合语法'.format(i+1, s[i])))
            break
        # 状态转移
        state = DFA.loc[state, s[i]]
        if int(i) != int(len(s) - 1):
            print(state, end='==>')
        else:
            print(state)

        # 判断序列是否含有非法符号，有则终止循环
        if  state not in DFA.index:
            print(format('\n第{0}个字符{1}不符合语法'.format(i+1, s[i])))
            break

    # 判断是否匹配成功
    if state in end_states:  # 在终态集中则符合
        print('{0}符合词法定义'.format(sequence))
        return True
    else:
        # 卡在的状态state
        print('{0}不符合词法定义'.format(sequence))
        return False


"""
    正则式支持escape/
"""
if __name__ == '__main__':
    from SourceCode.ex1.thompson.code import main

    if __name__ == '__main__':
        print("-------程序开始------")
        # regex=input("输入正规式:")
        # regex="(sin|cos|tg|ctg|log|lg|ln)#((PI|E|x)#)(#+|#-|#*|#/)(1|2|3|4|5|6|7|8|9)*"
        # regex="sin#(PI0#)#+(1|2|3|4|5|6|7|8|9)*"
        regex="(a|b)*abb"
        NFA, characters,start_state,end_state= main(regex)  # 如果状态包含end_state，则为终止状态
    characters[0] = ''


    # characters = ['', 'a', 'b']
    # NFA = [[], [0, 1], [0],
    #        [], [], [2],
    #        [], [], [3],
    #        [], [], []]
    # print(NFA)
    # NFA = np.array(NFA, dtype=object)
    # NFA = NFA.reshape(int(len(NFA) / len(characters)), len(characters))
    # print("NFA:", NFA)

    print("NFA的起始状态{0}，终止状态{1}".format(start_state,end_state))
    DFA,end_states= nfa_2_dfa(NFA, characters,start_state,end_state) # DFA的终态和DFA
    NFA=pd.DataFrame(NFA)
    characters[0] = 'ε'
    NFA.columns=characters
    # 打印
    print("NFA:")
    print(NFA)
    print("DFA(终止状态{0}):".format(end_states))
    print(DFA)  # pandas df结果

    # sequence = 'abb'
    # sequence = 'abab'
    # sequence = 'abc'
    print()
    sequence=input("输入测试字符串:")
    test_DFA(DFA, sequence,end_states)
    print()
    while True:
        sequence=input("再次输入测试字符串(输入退出，退出测试):")
        if sequence== "退出":
            break
        test_DFA(DFA,sequence,end_states)
        print()
    print("-------程序结束---------")